package com.shm.leetcode;

import java.math.BigInteger;
import java.util.Arrays;

/**
 * 5502. 将子数组重新排序得到同一个二叉查找树的方案数
 * 给你一个数组 nums 表示 1 到 n 的一个排列。我们按照元素在 nums 中的顺序依次插入一个初始为空的二叉查找树（BST）。请你统计将 nums 重新排序后，统计满足如下条件的方案数：重排后得到的二叉查找树与 nums 原本数字顺序得到的二叉查找树相同。
 *
 * 比方说，给你 nums = [2,1,3]，我们得到一棵 2 为根，1 为左孩子，3 为右孩子的树。数组 [2,3,1] 也能得到相同的 BST，但 [3,2,1] 会得到一棵不同的 BST 。
 *
 * 请你返回重排 nums 后，与原数组 nums 得到相同二叉查找树的方案数。
 *
 * 由于答案可能会很大，请将结果对 10^9 + 7 取余数。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：nums = [2,1,3]
 * 输出：1
 * 解释：我们将 nums 重排， [2,3,1] 能得到相同的 BST 。没有其他得到相同 BST 的方案了。
 * 示例 2：
 *
 *
 *
 * 输入：nums = [3,4,5,1,2]
 * 输出：5
 * 解释：下面 5 个数组会得到相同的 BST：
 * [3,1,2,4,5]
 * [3,1,4,2,5]
 * [3,1,4,5,2]
 * [3,4,1,2,5]
 * [3,4,1,5,2]
 * 示例 3：
 *
 *
 *
 * 输入：nums = [1,2,3]
 * 输出：0
 * 解释：没有别的排列顺序能得到相同的 BST 。
 * 示例 4：
 *
 *
 *
 * 输入：nums = [3,1,2,5,4,6]
 * 输出：19
 * 示例  5：
 *
 * 输入：nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
 * 输出：216212978
 * 解释：得到相同 BST 的方案数是 3216212999。将它对 10^9 + 7 取余后得到 216212978。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 1000
 * 1 <= nums[i] <= nums.length
 * nums 中所有数 互不相同 。
 * @author SHM
 */
public class NumOfWaysBST {
    int G = 1000000007;

    /**
     * 由题意可得：要使重排 nums 后，与原数组 nums 得到相同二叉查找树，则左右子树插入的相对次序不能变。
     *
     * 如[3,4,5,1,2]
     * 左子树为[1,2],右子树为[4,5]
     * 它的结果是：
     * [3,1,2,4,5]
     * [3,1,4,2,5]
     * [3,1,4,5,2]
     * [3,4,1,2,5]
     * [3,4,1,5,2]
     * 可见[1,2] 和 [4,5] 在结果中的次序都没有改变。 1始终在2左边，4始终在5左边
     *
     * 如何求有几种组合方法呢？就是C(左子树+右子树的数量,左子树的数量)
     * 如上：从4个结点中，取2个结点，即有C(4,2)种取法。
     *
     * 如此进行不断查找子结点中的组合数量，递归查询则可得到结果。
     *
     * 作者：saochuan888
     * 链接：https://leetcode-cn.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/solution/javadi-gui-by-saochuan888/
     * @param nums
     * @return
     */
    public int numOfWays(int[] nums) {
        long count = getCount(nums);
        if (count==0) {
            return G-1;
        }
        return (int)(count-1);
    }

    private long C(int big,int small){
        int a=1;
        int b=big;
        BigInteger res = BigInteger.valueOf(1);
        for (int i = 0; i < small; i++) {
            res = res.multiply(BigInteger.valueOf(b)).divide(BigInteger.valueOf(a));
            b--;
            a++;
        }
        return res.remainder(BigInteger.valueOf(G)).longValue();
    }

    private long getCount(int[] nums) {
        if (nums.length<=1){
            return 1;
        }
        int mid = nums[0];
        int[] smaller = Arrays.stream(nums).filter(item->item<mid).toArray();
        int[] bigger = Arrays.stream(nums).filter(item->item>mid).toArray();
        long n = C(nums.length-1,Math.min(smaller.length,bigger.length));
        //父结点结果需要和左右子树的结果相乘。
        long result = ((getCount(smaller)*getCount(bigger))%G)*n%G;
        return result;
    }
}
